package com.zjj.algorithm.learning.atguigu.algorithm;

import java.util.*;

/**
 * 最小生成树
 *
 * @author zjj_admin
 * @date 2023/1/3 20:53
 */
public class MinTree {

    /**
     * 创建图
     *
     * @param graph  图
     * @param vertex 图的顶点个数
     * @param data   图的顶点数据
     * @param weight 图的边
     */
    public void createGraph(Graph graph, int vertex, char[] data, int[][] weight) {
        int i, j;
        for (i = 0; i < vertex; i++) {
            graph.data[i] = data[i];
            for (j = 0; j < vertex; j++) {
                graph.weight[i][j] = weight[i][j];
            }
        }
    }

    /**
     * 展示图
     *
     * @param graph
     */
    public void showGraph(Graph graph) {
        System.out.println("图的结构如下：");
        for (int[] link : graph.weight) {
            System.out.println(Arrays.toString(link));
        }
    }


    /**
     * 使用prime算法创建最小生成树
     * 算法思想：
     * 选择一个起点，采用广度优先遍历获取最短的邻接节点。
     * 之后继续从访问节点中查找最小的没有访问的领节点
     *
     * @param graph 图
     * @param v     起点索引
     */
    public Map<String, Object> prime(Graph graph, int v) {
        Map<String, Object> res = new HashMap<>();
        List<String> pathList = new ArrayList<>();
        //visitedIndex 用于存储已经访问了的节点索引
        Set<Integer> visitedIndex = new HashSet<>();
        //初始化起点，就以索引为 0 的节点开始
        visitedIndex.add(v);
        int minLength = 0;
        while (true) {
            int start = 0;
            int end = 0;
            int min = Integer.MAX_VALUE;
            //遍历已经访问了的多有的节点
            for (Integer index : visitedIndex) {
                //当前节点的多有的邻接点
                int[] link = graph.weight[index];
                //遍历每一个临界点
                for (int i = 0; i < link.length; i++) {
                    //若当前可以连通并且 在 visitedIndex 中没有，并且距离小于当前最小
                    if (link[i] > 0 && !visitedIndex.contains(i) && link[i] < min) {
                        start = index;
                        end = i;
                        min = link[i];
                    }
                }
            }
            minLength += min;
            //将终点存入 visitedIndex
            visitedIndex.add(end);
            String path = graph.data[start] + " " + graph.data[end] + " ->" + graph.weight[start][end];
            pathList.add(path);
            //当所有的节点都访问了之后就退出即可
            if (visitedIndex.size() >= graph.vertex) {
                break;
            }
        }
        res.put("paths", pathList);
        res.put("shortestPath", minLength);
        return res;
    }


    /**
     * 使用 kruskal 算法构建最小生成树
     * 基本思路：按照权值从小到大选择 n - 1 条边，并保证这 n - 1 条边不产生回路
     * 难点：判断添加一个边之后有没有产生回路，将入的一个个边的两个点点是不是指向同一个终点
     *
     * @param graph
     * @return 生成的路劲
     */
    public List<GraphPath> kruskal(Graph graph) {
        int vertex = graph.vertex;
        //需要将图中的所有的路劲按照从小到大的顺序排序
        List<GraphPath> graphPaths = new ArrayList<>();
        int[][] weight = graph.weight;
        char[] data = graph.data;
        char start;
        char end;
        for (int i = 0; i < weight.length; i++) {
            for (int j = i; j < weight[i].length; j++) {
                //当顶点之间存在路劲时
                if (weight[i][j] > 0) {
                    start = data[i];
                    end = data[j];
                    GraphPath graphPath = new GraphPath(start, end, weight[i][j]);
                    graphPaths.add(graphPath);

                }
            }
        }
        //按照路劲大小进行排序
        Collections.sort(graphPaths);
        //定义一个 map ，保存目前每一个顶点的终点
        Map<Character, Character> loop = new HashMap<>();
        //对 graphPaths 进行遍历，找到 vertex - 1条最小的边，并且不能产生回路
        List<GraphPath> validPaths = new ArrayList<>();
        //依次遍历所有的边 graphPaths
        for (GraphPath graphPath : graphPaths) {
            if (validPaths.size() >= vertex - 1) {
                break;
            }
            char currStart = graphPath.start;
            char currEnd = graphPath.end;
            //首先判断 currEnd 和 currStart 的终点是否相同
            if (loop.containsKey(currEnd) && loop.containsKey(currStart)) {
                //只有当终点不同时，才不会有环路，说明可以取
                if (!loop.get(currStart).equals(loop.get(currEnd))) {
                    validPaths.add(graphPath);
                    //先计算 endPoint 的终点信息
                    createDestination(loop, validPaths, currEnd);
                    //再继续计算 startPoint 的终点信息
                    createDestination(loop, validPaths, currStart);
                    //这时需要对节点的终点进行修复
                    restoreLoop(loop, validPaths);
                }
            } else {
                validPaths.add(graphPath);
                //先计算 endPoint 的终点信息
                createDestination(loop, validPaths, currEnd);
                //再继续计算 startPoint 的终点信息
                createDestination(loop, validPaths, currStart);
                //这时需要对节点的终点进行修复
                restoreLoop(loop, validPaths);
            }
        }

        return validPaths;

    }


    /**
     * 获取顶点的终点
     *
     * @param loop
     * @param validPaths
     * @param point
     */
    private static void createDestination(Map<Character, Character> loop, List<GraphPath> validPaths, char point) {
        char currPoint = point;
        //获取终点信息
        Character destination = loop.get(currPoint);
        if (null == destination) {
            loop.put(point, currPoint);
        } else {
            currPoint = destination;
            //获取 currEnd 的终点信息
            for (GraphPath validPath : validPaths) {
                if (currPoint == validPath.start) {
                    if (loop.containsKey(currPoint)) {
                        loop.put(point, loop.get(currPoint));
                        break;
                    }
                }
            }
        }


    }

    /**
     * 对回路进行修复，重新刷新每一个顶点的终点
     *
     * @param loop
     * @param validPaths
     */
    private static void restoreLoop(Map<Character, Character> loop, List<GraphPath> validPaths) {


        for (Map.Entry<Character, Character> entry : loop.entrySet()) {
            Character start = entry.getKey();
            //获取当前顶点的终点信息
            Character destination = entry.getValue();
            //从已经存在边中获取起点和结束点的信息
            for (GraphPath validPath : validPaths) {
                //如果当前的终点
                if (destination.equals(validPath.start)) {
                    destination = validPath.end;
                    //判断在 loop 中是否存在起点为 end 的key
                    if (loop.containsKey(destination)) {
                        //当存在时，更新
                        destination = loop.get(destination);
                        loop.put(start, destination);
                        break;
                    }
                }
            }

        }
        //获取最大的终点信息
        char maxDestination = ' ';
        for (Map.Entry<Character, Character> entry : loop.entrySet()) {
            maxDestination = (char) Math.max(maxDestination, entry.getValue());
        }
        //根据最大的终点信息及可用路径刷新每一个节点的终点信息
        for (GraphPath validPath : validPaths) {
            if (validPath.start == maxDestination) {
                loop.put(validPath.start, maxDestination);
            }
            if (validPath.end == maxDestination) {
                //起点的当前终点
                Character currDestination = loop.get(validPath.start);
                for (Map.Entry<Character, Character> entry : loop.entrySet()) {
                    if (entry.getValue().equals(currDestination)) {
                        entry.setValue(maxDestination);
                    }
                }
            }
        }

    }


    /**
     * 使用 dijkstra 求最短路劲
     *
     * @param vertex 顶点信息
     * @param weight 图
     * @param start  起始顶点
     */
    public VisitedVertex dijkstra(char[] vertex, int[][] weight, char start) {
        VisitedVertex visitedVertex = new VisitedVertex(vertex, start);
        //更新 index 下标到其他周围顶点的距离和前驱顶点
        updateDistAndPre(start, visitedVertex, weight);
        for (int i = 1; i < vertex.length; i++) {
            Character newStart = visitedVertex.getNewStart();
            if (newStart != ' ') {
                visitedVertex.alreadyVisited.put(newStart, 1);
                updateDistAndPre(newStart, visitedVertex, weight);
            }
        }
        return visitedVertex;

    }

    /**
     * dijkstra 算法更新 point 下标到其他周围顶点的距离和前驱顶点
     *
     * @param point         当前顶点
     * @param visitedVertex
     * @param weight
     */
    public void updateDistAndPre(char point, VisitedVertex visitedVertex, int[][] weight) {
        int len;
        int index = visitedVertex.getIndex(point);
        for (int i = 0; i < weight[index].length; i++) {
            // len : 出发顶点到 point 的距离 + point 到 point 邻接顶点的距离
            if (weight[index][i] > 0) {
                len = visitedVertex.getDist(point) + weight[index][i];
                Character pointI = visitedVertex.getPoint(i);
                //当 顶点 i（pointI） 没有被访问过，或者 pointI 被访问过并且 len 小于出发顶掉到 i 的距离时，就需要更新
                //当 pointI 没有被访问过时
                if (visitedVertex.getDist(pointI) == -1) {
                    //此时一定没有被访问
                    visitedVertex.updatePre(pointI, point);
                    visitedVertex.updateDist(pointI, len);
                    visitedVertex.alreadyVisited.put(point, 1);
                } else {
                    //此时有可能被访问过，但是此时的路劲小于之前的路劲
                    if (len < visitedVertex.getDist(pointI)) {
                        visitedVertex.updatePre(pointI, point);
                        visitedVertex.updateDist(pointI, len);
                        visitedVertex.alreadyVisited.put(point, 1);
                    }
                }

            }
        }
    }


    /**
     * 使用 Floyd 算法求最短路劲
     * 以每一个节点为中间节点（例如 A），获取类似 BAF，BAG，FAG（其中B、F、G都和A相邻）
     * 检查 BAF 的路劲长度是否小于 BF，若小于就更新即可
     * 然后循环表里
     *
     * @param passage
     */
    public void floydAlgorithm(FloydPassage passage) {
        int[][] dist = passage.dist;
        char[][] pre = passage.pre;
        for (Map.Entry<Character, Integer> entry : passage.pointIndex.entrySet()) {
            Integer index = entry.getValue();
            //allPass 用来保存和 point 相邻的所有的邻接顶点的索引
            List<Integer> allPassIndex = new ArrayList<>();
            for (int i = 0; i < dist[index].length; i++) {
                //说明两个点之间可以通行
                if (dist[index][i] != -1) {
                    allPassIndex.add(i);
                }
            }
            //定义一个 pass 用于所有保存 如 BAF 类型中 B 和 F 的索引
            List<List<Integer>> pass = new ArrayList<>();
            for (int i = 0; i < allPassIndex.size(); i++) {
                for (int j = i + 1; j < allPassIndex.size(); j++) {
                    List<Integer> passI = new ArrayList<>();
                    passI.add(allPassIndex.get(i));
                    passI.add(allPassIndex.get(j));
                    pass.add(passI);
                }
            }
            for (List<Integer> passI : pass) {
                Integer index1 = passI.get(0);
                Integer index2 = passI.get(1);
                //获取 index 到 index1 和 index 和index2 的长度之和 是小于 index1 和 index2 之间的距离，是就更新
                int start = Math.min(index1, index);
                int end = Math.max(index1, index);
                //第一段距离长度
                int len1 = dist[start][end];
                start = Math.min(index2, index);
                end = Math.max(index2, index);
                //第二段距离长度
                int len2 = dist[start][end];
                //只要当 len1 + len2 小于 dist[index1][index2] 时就更新数据，dist[index1][index2] = -1 时为 最大，也要更新
                if (dist[index1][index2] == -1 || (len1 + len2) < dist[index1][index2]) {
                    dist[index1][index2] = len1 + len2;
                    dist[index2][index1] = len1 + len2;
                }
            }
        }
    }


}
